Chaum-Pedersen ZKP Protocol

The Chaum-Pedersen Zero-Knowledge Proof (ZKP) Protocol is a cryptographic method for proving the equality of discrete logarithms without revealing the secret exponent. It ensures that for given group elements $(g, h, A, B)$, there exists a secret $x$ such that $A = g^x$ and $B = h^x$.

Core Protocol Workflow

Setup

Public parameters: Cyclic group $G$ with prime order $q$, generators $g, h \in G$.
Prover's secret: $x \in \Bbb{Z}_q$
Public values: $A = g^x , B=h^x$

Commitment (Prover):

Choose random: $w \in \Bbb{Z}_q$
Compute commitments $t_1 = g^w, t_2 = h ^w$
Send $(t_1, t_2)$ to the verifier

Challenge (Verifier):

Generate random challenge $c \in \Bbb{Z}_q$
Send $c$ to the Prover.

Response (Prover):

Compute $s = w + c * x \mod q$
Send $s$ to the verifier

Verification:

Check $g^s \overset{?}{=} t_1 * A^c$
Check $h^s \overset{?}{=} t_2 * B^c$
Accept if both hold; reject otherwise

Proof

$$ \begin{align*} g^{s} &= g^{w + c * x \mod q} = g^w g^{cx} \mod q \newline t_1 * A^c &= g^w * (g^x)^c = g^w g^{cx} \mod q \newline & \implies g^s = t_1 * A^c \end{align*} $$

Similarly, can prove that $h^s = t_2 * B^c$